/**
 * 给定字符串，满足条件的子串数量：
 * 1. 元音字母与辅音字母数量相等
 * 2. 元音数量 * 辅音数量是K的倍数， K是预先给定的
 * N在1000，用前缀和设计O(N^2)即可
 */
class Solution {
public:
    int beautifulSubstrings(string s, int k) {
        int n = s.length();
        vector<int> ca(n), cb(n);
        if(isyuan(s[0])) ca[0] = 1, cb[0] = 0;
        else ca[0] = 0, cb[0] = 1;

        for(int i=1;i<n;++i){
            if(isyuan(s[i])) ca[i] = ca[i - 1] + 1, cb[i] = cb[i - 1];
            else ca[i] = ca[i - 1], cb[i] = cb[i - 1] + 1;
        }

        int ans = 0;
        for(int i=0;i<n;++i)for(int j=i;j<n;++j){
            int a = ca[j];
            if(i) a -= ca[i - 1];
            int b = cb[j];
            if(i) b -= cb[i - 1];

            if(a == b and a * b % k == 0) ++ans;
        }
        return ans;
    }

    bool isyuan(char ch){
        return ch == 'a' or ch == 'e' or ch == 'i' or ch == 'o' or ch == 'u';
    }
};